package day_2022_4_to_7.nowcoder;

import java.util.LinkedHashMap;
import java.util.Map;

/**
 * 斐波那契数列
 * @author haomin
 * @date 2022/04/11 19:22
 **/
public class FibonacciSequence_6f {
    public static void main(String[] args) {
        int n = 3;

        long star1 = System.nanoTime();
        System.out.print(Fibonacci1(n));
        long end1 = System.nanoTime();
        System.out.println(" Fibonacci1 递归排序结束,共耗时:" + (end1 - star1) / 1000000.0 + "ms");

        long star2 = System.nanoTime();
        System.out.print(Fibonacci2(n));
        long end2 = System.nanoTime();
        System.out.println(" Fibonacci2 非递归排序结束,共耗时:" + (end2 - star2) / 1000000.0 + "ms");
    }

    // 递归 但是此算法时间复杂度太大
    public static int Fibonacci1(int n) {
        if(n == 1 || n ==2){
            return 1;
        }
        return Fibonacci1(n - 1)+Fibonacci1(n - 2);
    }

    // 迭代 a,b,c
    public static int Fibonacci2(int n) {
        if(n == 1 || n ==2){
            return 1;
        }
        int a = 1;
        int b = 1;
        int c =0;
        for (int i = 3; i <= n; i++) {
            c = a + b;
            a = b;
            b = c;
        }
        return c;
    }

    // “减枝”思想，利用Map 将已得到的fib 存储起来
    private Map<Integer,Integer>  filter = new LinkedHashMap<>();
    public int Fibonacci3(int n) {
        if(n == 0){
            return 0;
        }
        if(n == 1 || n == 2){
            return 1;
        }

        int pre = 0;
        if(filter.containsKey(n-1)){
            // filter 已存在n-1的斐波那契数
            pre = filter.get(n-1);
        }else {
            // 不存在
            pre = Fibonacci3(n - 1);
            // 将该pre 存入filter中
            filter.put(n-1,pre);
        }

        int ppre = 0;
        if( filter.containsKey(n - 2)){
            // filter 已存在n-2的斐波那契数
            ppre = filter.get(n-2);
        }else {
            ppre = Fibonacci3(n-2);
            filter.put(n - 2,ppre);
        }

        return pre + ppre;
    }
}